#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
typedef char DataType;

typedef struct Node 
{
	DataType data;/*数据域*/
	struct Node *leftChild;/*左子树指针*/
	struct Node *rightChild;/*右子树指针*/
} BiTreeNode;/*结点的结构体定义*/
#define OK 0
#define ERRO 1
int _create_tree(BiTreeNode **root_pp,char * pre_order_seq,int *current_index){
	int status_sub_tree;
	if(pre_order_seq[*current_index] == '\0'){
		//TODO
		(*root_pp) = NULL;
		return OK;
	}
	if(pre_order_seq[*current_index] == '#'){
		*root_pp = NULL;
		//需要消耗掉这个#字符，因此*current-indez 需要+1
		*current_index += 1;
		return OK;
	}
	(*root_pp)= (BiTreeNode*)malloc(sizeof(BiTreeNode));
	if(!(*root_pp)){
		printf("failed to allocate memory,now exit()");
		return ERRO;
	}
	(*root_pp)->data = pre_order_seq[*current_index];
	*current_index += 1;
	status_sub_tree = _create_tree(&((*root_pp)->leftChild),pre_order_seq, current_index);
	if(status_sub_tree == ERRO){ 
		return status_sub_tree;
	}
	status_sub_tree = _create_tree(&((*root_pp))->rightChild,pre_order_seq,current_index);
	if(status_sub_tree == ERRO){
		return status_sub_tree;
	}
	return OK;
}
void create_tree(BiTreeNode ** root_pp, char * pre_order_seq,int num_elements) {
	int num_scanned_chars=0;
	_create_tree(root_pp, pre_order_seq,&num_scanned_chars);
	num_elements = num_elements;
	//	num_scanned_chars num_elements
}
//使用visit(item)函数前序来遍历二叉树t
void pre_order_traverse(BiTreeNode *t,void visit(DataType item)){
	if(t == NULL){
		return ;
	}
	visit (t->data);
	pre_order_traverse(t->leftChild, visit);
	pre_order_traverse(t->rightChild, visit);
}
//使用visit(item)函数中序遍历二叉树t
void in_order_traverse(BiTreeNode *t, void visit(DataType item)){
	if(t == NULL){
		return ;
	}
	in_order_traverse(t->leftChild, visit);
	visit (t->data);
	in_order_traverse(t->rightChild, visit);
}
//使用visit(item)函数后序序遍历二叉树t
void post_order_traverse(BiTreeNode *t, void visit(DataType item))
{
	if(t == NULL){
		return ;
	}
	post_order_traverse(t->leftChild, visit);
	post_order_traverse(t->rightChild, visit);
	visit (t->data);
	
	
}
// 可以无需更改本函数的实现
void visit(DataType item)
{
	printf("%c ", item);
}

// 查找元素值x是否在二叉树中
// 如果找到，返回值为x的结点的指针，否则返回NULL
BiTreeNode * search(BiTreeNode *root, DataType x)
{
	BiTreeNode *find;
	//空树找不到
	if (root == NULL)
		return NULL;
	if (root->data == x)  // 找到了返回 root
		return root;
	//查找左右子树
	find = search(root->leftChild, x);
	if (find)  //不为空就继续查找
		return find;
	return search(root->rightChild, x);
	
}
// 递归地销毁由 *root 所指向根节点的树：释放该树涉及的所有动态分配的内存空间
void destroy(BiTreeNode **root)
{
	BiTreeNode* cur = *root;
	if (cur) {
		destroy(&cur->leftChild);
		destroy(&cur->rightChild);
		free(cur);
		*root = NULL;
	}
	
}
int main() {
	
	BiTreeNode* root_pp;
	create_tree(&root_pp,"ABC##DE#G##F###", 21 );
	pre_order_traverse(root_pp, visit);
	in_order_traverse(root_pp,  visit);
	post_order_traverse(root_pp, visit);
	
	
	
	
	
}
